\documentclass[12pt,a4paper]{article}

\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{colortbl}
\usepackage[T1]{fontenc}
\usepackage{times}
\usepackage{tikz}
\usepackage{anysize} % Soporte para el comando \marginsize
%\marginsize{2.5cm}{1.5cm}{1.5cm}{1.5cm}

\usepackage{color}    % aunque tambien puedes usar xcolor
\definecolor{gray97}{gray}{.97}
\definecolor{gray75}{gray}{.75}
\definecolor{gray45}{gray}{.45}

\usepackage{listings}
\lstset{ frame=Ltb,
     framerule=0pt,
     aboveskip=0.5cm,
     framextopmargin=2pt,
     framexbottommargin=2pt,
   %  framexleftmargin=-1.0cm,
  %   framexrightmargin=0cm,     
     framesep=0pt,
     rulesep=.4pt,
     backgroundcolor=\color{gray97},
     rulesepcolor=\color{black},
     %
     stringstyle=\ttfamily,
     showstringspaces = false,
     basicstyle=\small\ttfamily,
     commentstyle=\color{gray45},
     keywordstyle=\bfseries,
     %
     numbers=left,
     numbersep=15pt,
     numberstyle=\tiny,
     numberfirstline = false,
     breaklines=true,
   }
\lstdefinestyle{Cpp}
   {language=C++,
   }

% Definición de los grupos
\author{Bortoli Leonardo - Campo David - Del Castillo Sergio}
\date{\today}
\title{Trabajo Práctico Final\\
       Programación Competitiva}

\begin{document}

\maketitle
\thispagestyle{empty}
\newpage
\tableofcontents
\thispagestyle{empty}
\newpage

% Problemas:

\section{Strategic Defense Initiative}

\subsection{Caracterización de la estructura de una solución óptima}
Sean $X = \{x_1, x_2,\ldots , x_n\}$ y $C = \{c_1, c_2,\ldots , c_n\}$ secuencias de elementos, donde $X$ representa los datos de entrada y $C$ representa la longitud de la subsecuencia creciente máxima hasta cada elemento de $X$.\\
Tomando los elementos $x_i$ y $x_j$ pertenecientes al conjunto $X$, donde $i \leq j$, definimos
las siguientes propiedades:
\begin{itemize}
\item Si $i = j \Rightarrow c_j$ es el LIS de $X_j$
\item Si $x_j > x_i \Rightarrow c_i$ es el LIS que incluye dicho elemento, $\forall i \in [1; j]$
\item Si $x_j > x_i \land c_j < c_i + 1 \Rightarrow c_i$ es el LIS hasta dicho elemento, $\forall i \in [1; j)$
\end{itemize}

\subsection{Definir una solución recursiva}
Sea $c_{max}$ un elemento de la secuencia $C$ que representa el máximo valor, o sea, es el LIS de la secuencia $X$.
Ahora, a cada elemento de la secuencia $C$ se lo define recursivamente de la siguiente forma:
$$
c_i = \left\{ 
\begin{array}{ll}
1 & \qquad i = j\\
max(c_j, c_i + 1) & \qquad \forall i \in [1;j) \land  x_j > x_i
\end{array}
\right.
$$

La solución del problema viene dada por la siguiente fórmula:
$$ LIS(X) = c_{max} = max(c_i) \quad \forall i \in [1;n] $$

\subsection{Implementación con Bottom-Up y Top-Down}
\begin{lstlisting}[style=Cpp]
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include <sstream>
#include <limits>

using namespace std;

const int NINF = numeric_limits<int>::min();
vector<int> cost;   // vector de costos
vector<int> parent; // vector de padres

int recursive_top_down(const vector<int>& input, int i) {
   if(cost[i] > NINF) {
      return cost[i];
   }

   cost[i] = 1;

   for(int j = i-1; j >= 0; j--){   
      int cj = recursive_top_down(input, j);

      if(input[j] < input[i]) {
         cost[i] = max(cost[i], cj + 1);

         if (cost[i] == cj + 1) {
            parent[i] = j;               
         }
      }
   }
   
   return cost[i];
}

int top_down(const vector<int>& input) {
   cost  .assign(input.size(), NINF);
   parent.assign(input.size(), -1);
   
   cost[0] = 1;

   recursive_top_down(input, input.size() - 1);

   int index = 0;
      
   for(unsigned i = 1; i < cost.size(); i++){
      if(cost[i] > cost[index]){
         index = i;
      }
   }
   
   return index;
}

int bottom_up(const vector<int>& input){
   cost  .assign(input.size(),  1);
   parent.assign(input.size(), -1);
   
   for(unsigned i = 0; i < input.size(); i++){
      for(unsigned j = i+1; j < input.size(); j++){
         if(input[j] > input[i]) {
            cost[j] = max(cost[j], cost[i] + 1);

            if (cost[j] == cost[i] + 1) {
               parent[j] = i;               
            }
         }
      }
   }
   
   int index = 0;
   
   for(unsigned i = 1; i < cost.size(); i++){
      if(cost[i] > cost[index]){
         index = i;
      }
   }
   
   return index;
}

void print(int index, const vector<int>& input){
   cout << "Max hits: " << cost[index] << endl;
   
   stack<int> s;
   s.push(input[index]);

   while(parent[index] != -1){
      s.push(input[parent[index]]);
      index = parent[index];
   }

   while(!s.empty()){
      cout << s.top() << endl;
      s.pop();
   }
}

int main(){
   int ncases, value;
   string line;
  
   cin >> ncases;
   cin.ignore();
   
   getline(cin, line);
   
   for(int k=0; k<ncases; k++){
      getline(cin, line);
      vector<int> input;

      while("" != line) {
         stringstream sin(line);         
         sin >> value;
         input.push_back(value);
         getline(cin, line);
      }

      #ifdef TOPDOWN
         print(top_down(input), input);
      #else
         print(bottom_up(input), input);
      #endif
      
      if((k+1) < ncases){
         cout << endl;
      }
   }
      
   return 0;
}
\end{lstlisting}

\subsection{Análisis de Complejidad}
\subsubsection{Enfoque Bottom-Up}
La función de tiempo $T(n)$ del algoritmo se define de la siguiente forma:
$$
T(n) = T_1(n) + T_2(n)
$$

Donde $T_1(n) $ es el tiempo de ejecución del código entre las líneas 61--72. El bucle {\bf for} de la línea 61
itera de $0$ a $n$ y el {\bf for} de la línea 62 itera de $i+1$ a $n$. En total la cantidad de iteraciones realizadas es: $$T_1(n) = k_1\,\frac{n(n-1)}{2}$$

La función $T_2(n)$ es el tiempo de ejecución del código entre las líneas 76--80.  Puesto que itera de $1$ a $n$ en forma lineal, tenemos que:
$$T_2(n)= k_2\,n$$

Finalmente obtenemos:
$$T(n) = k_1\,\frac{n(n-1)}{2}+k_2\,n$$

Con esta información podemos afirmar que la complejidad del algoritmo es $O(n^2)$.

\subsubsection{Enfoque Top-Down}
Este enfoque realiza aproximadamente la misma cantidad de operaciones que el algoritmo anterior, ya que utiliza la técnica 
de memorización para no recalcular datos ya obtenidos. Por lo tanto su complejidad es $O(n^2)$. Cabe aclarar que existe una pequeña sobrecarga asociada a este algoritmo debido a la pila de llamadas recursivas.

%---------------------------------

\section{String Distance and Edit Process}

\subsection{Caracterización de la estructura de una solución óptima}
Sean $X = x_1x_2\ldots x_n$ e $Y = y_1y_2\ldots y_m$ dos cadenas de caracteres, se desea hallar la mínima cantidad
de operaciones de edición $Z = \{z_1,z_2,\ldots ,z_k\}$ (inserción, modificación y eliminación) para convertir la cadena $X$ a la cadena $Y$.

Para dicho problema se cumplen las siguientes propiedades mutuamente excluyentes:
\begin{itemize}
\item Si $x_i \neq y_j \Rightarrow Z_{k-1}$ es la secuencia mínima de operaciones de edición de $X_{i-1}$ e $Y_{j-1}$ y la operación es {\sl modificación} 
\item Si $x_i \neq y_j \Rightarrow Z_{k-1}$ es la secuencia mínima de operaciones de edición de $X_{i}$ e $Y_{j-1}$ y la
operación es {\sl inserción}
\item Si $x_i \neq y_j \Rightarrow Z_{k-1}$ es la secuencia mínima de operaciones de edición de $X_{i-1}$ e $Y_{j}$ y la
operación es {\sl eliminación}
\end{itemize}

\subsection{Definir una solución recursiva}
De las propiedades anteriores definimos la siguiente solución recursiva, 
donde $c_{i,j}$ es el costo óptimo de operaciones asociado a las subcadenas $x_1x_2\ldots x_i$ e $y_1y_2\ldots y_j$:
$$
c_{i,j} = \left\{ 
\begin{array}{ll}
j & \qquad i = 0\\
i & \qquad j = 0\\
c_{i-1,j-1} & \qquad i,j > 0 \land x_i = y_j\\
1 + min(c_{i-1,j},c_{i,j-1},c_{i-1,j-1}) & \qquad i,j > 0 \land x_i \neq y_j
\end{array}
\right.
$$

\subsection{Implementación con Bottom-Up y Top-Down}
\begin{lstlisting}[style=Cpp]
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>

using namespace std;

const int INF = numeric_limits<int>::max();

vector< vector<int> > c;
vector< vector<char> > p;

int recursive_top_down(const string& a, const string& b, unsigned i, unsigned j) {
   if(c[i][j] < INF) {
      return c[i][j];
   }
   
   if(0 == i) {
      return j;
   }
   
   if(0 == j) {
      return i;
   }

   if(a[j - 1] == b[i - 1]) {
      p[i][j] = 'n';
      return (c[i][j] = recursive_top_down(a, b, i - 1, j - 1));
   }
   
   int x, y, z;   
   x = recursive_top_down(a, b, i, j - 1);
   y = recursive_top_down(a, b, i - 1, j);
   z = recursive_top_down(a, b, i - 1, j - 1);

   c[i][j] = min(x, min(y, z));

   if(c[i][j] == x){ // eliminacion
      p[i][j] = 'd';
   } else if(c[i][j] == y){ // insercion
      p[i][j] = 'i';       
   } else { // reemplazo
      p[i][j] = 'r';                        
   }

   return ++c[i][j];
}

int top_down(string& a, string& b){
   c.resize(b.size() + 1);
   p.resize(b.size() + 1);

   for(unsigned i = 0; i < c.size(); i++){
      c[i].resize(a.size()+1);
      p[i].resize(a.size()+1);
   }
   
   for(unsigned i = 0; i < c.size(); i++){
      c[i][0] = i;
      p[i][0] = 'i';
   }
   
   for(unsigned j = 0; j < c[0].size(); j++){
      c[0][j] = j;
      p[0][j] = 'd';
   }
   
   for(unsigned i = 1; i < c.size(); i++) {
      for(unsigned j = 1; j < c[0].size(); j++) {
         c[i][j] = INF;
      }
   }   
   
   p[0][0] = '*';
   
   return recursive_top_down(a, b, b.size(), a.size());
}

int bottom_up(string& a, string& b){
   c.resize(b.size() + 1);
   p.resize(b.size() + 1);
      
   for(unsigned i = 0; i < c.size(); i++){
      c[i].resize(a.size()+1);
      p[i].resize(a.size()+1);
   }
   
   for(unsigned i = 0; i < c.size(); i++){
      c[i][0] = i;
      p[i][0] = 'i';
   }
   
   for(unsigned j = 0; j < c[0].size(); j++){
      c[0][j] = j;
      p[0][j] = 'd';
   }
   
   p[0][0] = '*';
     
   for(unsigned i = 1; i < c.size(); i++){
      for(unsigned j = 1; j < c[i].size(); j++){
         if(a[j-1] == b[i-1]){
            c[i][j] = c[i-1][j-1];
            p[i][j] = 'n';
         } else {
            c[i][j] = min(c[i][j-1], min(c[i-1][j], c[i-1][j-1]));
            
            if(c[i][j-1] == c[i][j]){ // eliminacion
               p[i][j] = 'd';
            } else if(c[i][j] == c[i-1][j]){ // insercion
               p[i][j] = 'i';            
            } else { // reemplazo
               p[i][j] = 'r';                        
            }

            c[i][j]++;
         }  
      }
   }

   return c[b.size()][a.size()];
}

void print_solution(string& a, string& b){
   int i = p.size()-1;
   int j = p[0].size()-1;
   vector<int> indexes;
   vector<char> operations, characters;
      
   while(p[i][j] != '*'){
      switch(p[i][j]){
         case 'd':
            operations.push_back('d');
            indexes.push_back(j);
            characters.push_back('-');
            j--;
            break;
         case 'i':
            operations.push_back('i');
            indexes.push_back(j+1);
            characters.push_back(b[i-1]);
            i--;            
            break;
         case 'r':
            operations.push_back('r');
            indexes.push_back(j);
            characters.push_back(b[i-1]);            
            i--;
            j--;
            break;
         default:
            i--;
            j--;
      }
   }
   
   reverse(indexes.begin(), indexes.end());
   reverse(operations.begin(), operations.end());
   reverse(characters.begin(), characters.end());
   
   int ds = 0;
   for(unsigned i=0; i<operations.size(); i++){
      switch(operations[i]){
         case 'd':
            cout << i+1 << " Delete " << indexes[i] + ds << endl;
            ds--;
            break;
         case 'r':
            cout << i+1 << " Replace " << indexes[i] + ds << ',' << characters[i] << endl;
            break;
         case 'i':
            cout << i+1 << " Insert " << indexes[i] + ds << ',' << characters[i] << endl;
            ds++;
      }
   }
}

int main(){
   string a, b;
   bool print_endl = false; 
   
   while(getline(cin, a) && getline(cin, b)) {
      if(print_endl)
         cout << endl;
      else 
         print_endl = true;
         
      #ifdef TOPDOWN   
         cout << top_down(a, b) << endl;
      #else
         cout << bottom_up(a, b) << endl;
      #endif
      
      print_solution(a, b);
      c.clear();
      p.clear();      
   }
}
\end{lstlisting}

\subsection{Análisis de Complejidad}
\subsubsection{Enfoque Bottom-Up}
La función de tiempo $T(n)$ del algoritmo es el tiempo de ejecución del código entre las líneas 101--120. El bucle {\bf for} de la línea 101 itera de $1$ a $n$ y el {\bf for} de la línea 102 itera de $1$ a $m$. En total la cantidad de iteraciones realizadas es: $$T(n,m)= k\,n\,m$$

Con esta información podemos afirmar que la complejidad del algoritmo es $O(n\,m)$.

\subsubsection{Enfoque Top-Down}
Este enfoque realiza aproximadamente la misma cantidad de operaciones que el algoritmo anterior, ya que utiliza la técnica de memorización para no recalcular datos ya obtenidos. Por lo tanto su complejidad es $O(n\,m)$. Cabe aclarar que existe una pequeña sobrecarga asociada a este algoritmo debido a la pila de llamadas recursivas.

%---------------------------------

\section{Optimal Array Multiplication Sequence}

\subsection{Caracterización de la estructura de una solución óptima}
Sea una secuencia de matrices $A_1A_2\ldots A_n$, de la cual se desea obtener el producto de todas ellas.
El problema radica en encontrar una manera de asociar las matrices para su multiplicación, de forma tal de minimizar
la cantidad de operaciones escalares entre ellas.

Por ejemplo, sea la secuencia de matrices $A_1A_2A_3A_4$, dos posibles asociaciones podrían ser las siguientes:
$$
(A_1(A_2(A_3A_4)))
$$
$$
((A_1A_2)(A_3A_4))
$$

Definimos una forma estructurada de dividir la secuencia para poder encontrar una asociación óptima. Sean
$i$, $j$ y $k$ índices de la secuencia de matrices, donde $i \leq k < j$, seleccionamos $k$ para obtener una
partición binaria óptima, quedando dos subsecuencias disjuntas con asociaciones óptimas.
Finalmente, la asociación óptima para la secuencia original se obtiene uniendo ambas particiones, más el costo
de dicho cálculo.

\subsection{Definir una solución recursiva}
Utilizando la propiedad anterior, definimos una solución recursiva teniendo en cuenta que $m_{i,j}$ es el costo óptimo
de asociar la subcadena $A_iA_{i+1}\ldots A_j$:
$$
m_{i,j} = \left\{ 
\begin{array}{ll}
0 & \qquad i = j\\
min(m_{i,k}+m_{k+1,j}+p_{i-1}\,p_k\,p_j)\quad \forall k \in [i;j) & \qquad i<j
\end{array}
\right.
$$

En la fórmula anterior, $p_i$ representa el número de filas de la matriz $A_i\ \forall i<n$, y $p_n$ es el número de columnas de
la matriz $A_n$.

\pagebreak

\subsection{Implementación con Bottom-Up y Top-Down}
\begin{lstlisting}[style=Cpp]
#include <cstdio>
#include <iostream>
#include <vector>
#include <limits>

using namespace std;

vector<vector<unsigned> > m, s;

unsigned bottom_up(vector<unsigned>& p){
   unsigned n = p.size()-1;

   m.resize(n+1);
   s.resize(n+1);

   for(unsigned i = 0; i <= n; i++){
      m[i].assign(n+1, 0);
      s[i].assign(n+1, 0);
   }
	
   for(unsigned l = 2; l <= n; l++){
      for(unsigned i = 1; i <= n-l+1; i++){
         unsigned j = i+l-1;
         m[i][j] = numeric_limits<unsigned>::max();

         for(unsigned k = i; k < j; k++){
            unsigned q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];

            if(q < m[i][j]){
               m[i][j] = q;
               s[i][j] = k;
            }
         }
      } 
   }
   
   return m[1][n];
}

unsigned recursive_top_down(vector<unsigned>& p, unsigned i, unsigned j){
   if(m[i][j] < numeric_limits<unsigned>::max()){
      return m[i][j];
   }
   if(i == j){
      m[i][j] = 0;
   } else {
      for(unsigned k = i; k < j; k++){
         unsigned q = recursive_top_down(p, i, k) + recursive_top_down(p, k+1, j) + p[i-1] * p[k] * p[j];
         
         if(q < m[i][j]){
            m[i][j] = q;
            s[i][j] = k;
         }
      }
   }
   
   return m[i][j];
}

unsigned top_down(vector<unsigned>& p){
   unsigned n = p.size()-1;

   m.resize(n+1);
   s.resize(n+1);

   for(unsigned i = 0; i <= n; i++){
      m[i].assign(n+1, numeric_limits<unsigned>::max());
      s[i].assign(n+1, 0);
   }   
   
   return recursive_top_down(p, 1, n);
}

void print(int i, int j){
   if(i == j){
      printf("A%d", i);
   } else {
      printf("(");
      print(i, s[i][j]);
      printf(" x ");
      print(s[i][j]+1, j);		
      printf(")");
   }
}

int main(){
   unsigned n, r, c, count = 0;
   
   cin >> n;  
   while(n != 0){
      vector<unsigned> in;
      
      for(unsigned i = 0; i < n; i++){
         cin >> r >> c;
         in.push_back(r);
      }

      in.push_back(c);
      
      #ifdef TOPDOWN
         top_down(in);
      #else 
         bottom_up(in);
      #endif

      cout << "Case " << ++count << ": ";
      print(1, n);
      cout << endl;
      cin >> n;
   }
   
   return 0;
}
\end{lstlisting}


\subsection{Análisis de Complejidad}
\subsubsection{Enfoque Bottom-Up}
Para obtener la función de tiempo $T(n)$ del algoritmo utilizamos como ayuda la matriz de la siguiente figura:

\begin{figure}[h]\begin{center}
\begin{tikzpicture}
\matrix [nodes={draw,minimum size=1cm}]
{
\node[fill=black!60]{(1,1)}; & \node[fill=black!40]{(1,2)}; & \node[fill=black!30]{(1,3)}; & \node[fill=black!10]{{\bf (1,4)}}; \\
& \node[fill=black!10]{{\bf (2,2)}}; & \node[fill=black!10]{{\bf (2,3)}}; & \node[fill=black!60]{(2,4)}; \\
& & \node[fill=black!10]{{\bf (3,3)}}; & \node[fill=black!40]{(3,4)}; \\
& & & \node[fill=black!20]{(4,4)}; \\
};
\end{tikzpicture}\end{center}
\caption{Matriz de costos de $4 \times 4$}
\label{fig:matriz1}
\end{figure}

Siguiendo las lineas 21 y 22 del algoritmo, vemos que al finalizar el recorrido hecho por la doble sentencia \textbf{for}, 
se visitan solamente las celdas marcadas en la Figura 1. Ahora bien, si contamos la cantidad de celdas visitadas, obtenemos la siguiente fórmula:$$T_1(n)=k_1\,\frac{n(n+1)}{2}$$

Luego de esto, para calcular el valor óptimo de cada celda, se realizan en el peor caso $2(n-1)$ accesos. Esto lo podemos verificar
en la Figura 1, donde el par de valores $m_{0,k}$ y $m_{k+1,3}$ para cada iteración de $k$, son los que poseen el mismo color en la matriz de costos. De esta forma la función de tiempo es:
$$T_2(n)=k_2\,n$$


Finalmente, puesto que este último paso se realiza por cada iteración del doble \textbf{for}, la función de tiempo resultante es:
$$T(n) = T_1(n)\,T_2(n) = \left(k_1\,\frac{n(n+1)}{2}\right)\,\left(k_2\,n\right) = k\,\frac{n^2(n+1)}{2}$$

Por lo tanto, el orden de complejidad del algoritmo es $O(n^3)$.


\subsubsection{Enfoque Top-Down}
Este enfoque realiza aproximadamente la misma cantidad de operaciones que el algoritmo anterior, ya que utiliza la técnica 
de memorización para no recalcular datos ya obtenidos. Por lo tanto su complejidad es $O(n^3)$. Cabe aclarar que existe una pequeña sobrecarga asociada a este algoritmo debido a la pila de llamadas recursivas.
\end{document}
